package medium;

import java.util.*;

public class Lc39 {
    class Solution {

        private List<List<Integer>> ret = new ArrayList<>();

        private Set<String> retSet = new HashSet<>(); // 用于校验重复性

        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            dfs(candidates, target, new ArrayList<>());
            return ret;
        }

        /**
         * 对candidates中每个元素进行回溯
         * @param candidates 可选的元素集合
         * @param target 当前的目标
         * @param choice 当前已选的元素
         */
        private void dfs(int[] candidates, int target, List<Integer> choice) {
            // 边界，target = 0，符合 target < 0，不符合且停止递归
            if (target == 0) {
                choice.sort(Comparator.comparingInt(Integer::valueOf));
                if (!retSet.contains(choice.toString())) {
                    ret.add(new ArrayList<>(choice));
                    retSet.add(choice.toString());
                }
                return;
            } else if (target < 0) {
                return;
            }

            // 选，本题场景不能不选，至少选一个，不选会陷入无限递归
            for (int val : candidates) {
                List<Integer> newChoice = new ArrayList<>(choice);
                newChoice.add(val);
                dfs(candidates, target - val, newChoice);
            }
        }


    }
}
